package com.datastructures2.graph.最小生成树;


import com.datastructures2.tree2.BinaryHeap;
import com.datastructures2.unionFind.ComPathWeightedQuickUnionFind;
import com.datastructures2.背包队列栈.Queue;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/**
 * 最小生成树的Kruskal算法
 * @author MaoLin Wang
 * @date 2020/2/2316:44
 */
public class KruskalMST {
    /**
     * 最小生成树权重
     */
    private double weight=0.0;
    /**
     * 最小生成树所有边
     */
    private Queue<Edge> mst;

    public KruskalMST(EdgeWeightedGraph G){
        mst=new Queue<>();
        //创建一个优先队列
        BinaryHeap<Edge> pq= new BinaryHeap<>();
        for (Edge e: G.edges()){
            //将所有边加入队列中，按权重大小从小到大排序
            pq.insert(e);
        }
        //创建一个并查集
        ComPathWeightedQuickUnionFind uf=new ComPathWeightedQuickUnionFind(G.V());
        //队列非空且边的个数小于顶点数-1时循环
        while (!pq.isEmpty() && mst.size()<G.V()-1){
            //得到权重最小的边
            Edge edge = pq.deleteMin();
            int v=edge.either(),w=edge.other(v);

            if (uf.connected(v,w)){
                //忽略失效的边
                continue;
            }
            uf.union(v,w);//合并分量
            mst.enqueue(edge);//加入生成树
            weight+=edge.weight();


        }

    }
    public Iterable<Edge> edges(){
        return mst;
    }
    public double weight(){
        return weight;
    }

    public static void main(String[] args) {
        In in = new In("D:\\JavaProject\\算法\\数据结构和算法\\DATAStructures\\alg\\src\\main\\java\\com\\datastructures2\\graph\\最小生成树\\tinyEWG.txt");
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        KruskalMST mst = new KruskalMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }

        StdOut.printf("%.5f\n", mst.weight());

    }
}
